package com.xie.sort.insertsort;

import java.util.*;

/**
 * 桶排序
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};
        System.out.println("排序前:\n" + Arrays.toString(arr));
        // 插入排序
        bucketSort(arr);
        System.out.println("排序后:\n" + Arrays.toString(arr));
    }

    public static void bucketSort(int[] arr) {
        if (arr == null && arr.length == 0) {
            return;
        }

        //桶的索引
        List<List<Integer>> buckets = new ArrayList<List<Integer>>();

        //这里默认为10，规定待排数[0,100)
        int bucketNums = 10;
        for (int i = 0; i < bucketNums; i++) {
            //用链表比较合适
            buckets.add(new LinkedList<Integer>());
        }

        //划分桶
        for (int j : arr) {
            buckets.get(f(j)).add(j);
        }

        //对每个桶进行排序
        for (List<Integer> integers : buckets) {
            if (!integers.isEmpty()) {
                //对每个桶进行快排
                Collections.sort(integers);
            }
        }

        //还原排好序的数组
        int k = 0;
        for (List<Integer> bucket : buckets) {
            for (int ele : bucket) {
                arr[k++] = ele;
            }
        }
    }

    /**
     * 映射函数
     *
     * @param x 值
     * @return 桶标志
     */
    public static int f(int x) {
        return x / 10;
    }
}
